Adding some strings and geometry algorithms to notebook.

[andmenj-acm.git] / Mi manual de algoritmos / version_actual / manual.toc

\select@language {spanish}
\contentsline {section}{\numberline {1}Plantilla}{2}{section.1}
\contentsline {section}{\numberline {2}Teor\IeC {\'\i }a de n\IeC {\'u}meros}{2}{section.2}
\contentsline {subsection}{\numberline {2.1}Big mod}{2}{subsection.2.1}
\contentsline {subsection}{\numberline {2.2}Criba de Erat\IeC {\'o}stenes}{3}{subsection.2.2}
\contentsline {subsection}{\numberline {2.3}Divisores de un n\IeC {\'u}mero}{3}{subsection.2.3}
\contentsline {section}{\numberline {3}Combinatoria}{3}{section.3}
\contentsline {subsection}{\numberline {3.1}Cuadro resumen}{3}{subsection.3.1}
\contentsline {subsection}{\numberline {3.2}Combinaciones, coeficientes binomiales, tri\IeC {\'a}ngulo de Pascal}{3}{subsection.3.2}
\contentsline {subsection}{\numberline {3.3}Permutaciones con elementos indistinguibles}{4}{subsection.3.3}
\contentsline {subsection}{\numberline {3.4}Desordenes, desarreglos o permutaciones completas}{4}{subsection.3.4}
\contentsline {section}{\numberline {4}Grafos}{4}{section.4}
\contentsline {subsection}{\numberline {4.1}Algoritmo de Dijkstra}{4}{subsection.4.1}
\contentsline {subsection}{\numberline {4.2}Minimum spanning tree: Algoritmo de Prim}{5}{subsection.4.2}
\contentsline {subsection}{\numberline {4.3}Minimum spanning tree: Algoritmo de Kruskal + Union-Find}{5}{subsection.4.3}
\contentsline {subsection}{\numberline {4.4}Algoritmo de Floyd-Warshall}{6}{subsection.4.4}
\contentsline {subsection}{\numberline {4.5}Algoritmo de Bellman-Ford}{6}{subsection.4.5}
\contentsline {subsection}{\numberline {4.6}Puntos de articulaci\IeC {\'o}n}{7}{subsection.4.6}
\contentsline {subsection}{\numberline {4.7}M\IeC {\'a}ximo flujo: M\IeC {\'e}todo de Ford-Fulkerson, algoritmo de Edmonds-Karp}{8}{subsection.4.7}
\contentsline {subsection}{\numberline {4.8}M\IeC {\'a}ximo flujo para grafos dispersos usando Ford-Fulkerson}{9}{subsection.4.8}
\contentsline {subsection}{\numberline {4.9}Componentes fuertemente conexas: Algoritmo de Tarjan}{10}{subsection.4.9}
\contentsline {subsection}{\numberline {4.10}2-Satisfiability}{11}{subsection.4.10}
\contentsline {section}{\numberline {5}Programaci\IeC {\'o}n din\IeC {\'a}mica}{11}{section.5}
\contentsline {subsection}{\numberline {5.1}Longest common subsequence}{11}{subsection.5.1}
\contentsline {subsection}{\numberline {5.2}Partici\IeC {\'o}n de troncos}{12}{subsection.5.2}
\contentsline {section}{\numberline {6}Strings}{13}{section.6}
\contentsline {subsection}{\numberline {6.1}Algoritmo de Knuth-Morris-Pratt (KMP)}{13}{subsection.6.1}
\contentsline {subsection}{\numberline {6.2}Algoritmo de Aho-Corasick}{14}{subsection.6.2}
\contentsline {subsection}{\numberline {6.3}Suffix arrays y longest common prefix}{16}{subsection.6.3}
\contentsline {section}{\numberline {7}Geometr\IeC {\'\i }a}{18}{section.7}
\contentsline {subsection}{\numberline {7.1}\IeC {\'A}rea de un pol\IeC {\'\i }gono}{18}{subsection.7.1}
\contentsline {subsection}{\numberline {7.2}Centro de masa de un pol\IeC {\'\i }gono}{18}{subsection.7.2}
\contentsline {subsection}{\numberline {7.3}Convex hull: Graham Scan}{18}{subsection.7.3}
\contentsline {subsection}{\numberline {7.4}Convex hull: Andrew's monotone chain}{19}{subsection.7.4}
\contentsline {subsection}{\numberline {7.5}M\IeC {\'\i }nima distancia entre un punto y un segmento}{20}{subsection.7.5}
\contentsline {subsection}{\numberline {7.6}M\IeC {\'\i }nima distancia entre un punto y una recta}{20}{subsection.7.6}
\contentsline {subsection}{\numberline {7.7}Determinar si un pol\IeC {\'\i }gono es convexo}{20}{subsection.7.7}
\contentsline {subsection}{\numberline {7.8}Determinar si un punto est\IeC {\'a} dentro de un pol\IeC {\'\i }gono convexo}{21}{subsection.7.8}
\contentsline {subsection}{\numberline {7.9}Determinar si un punto est\IeC {\'a} dentro de un pol\IeC {\'\i }gono cualquiera}{21}{subsection.7.9}
\contentsline {subsection}{\numberline {7.10}Hallar la intersecci\IeC {\'o}n de dos rectas}{22}{subsection.7.10}
\contentsline {subsection}{\numberline {7.11}Hallar la intersecci\IeC {\'o}n de dos segmentos de recta}{22}{subsection.7.11}
\contentsline {subsection}{\numberline {7.12}Determinar si dos segmentos de recta se intersectan o no}{23}{subsection.7.12}
\contentsline {section}{\numberline {8}Estructuras de datos}{24}{section.8}
\contentsline {subsection}{\numberline {8.1}\IeC {\'A}rboles de Fenwick \IeC {\'o} Binary indexed trees}{24}{subsection.8.1}
\contentsline {subsection}{\numberline {8.2}Segment tree}{24}{subsection.8.2}
\contentsline {section}{\numberline {9}Miscel\IeC {\'a}neo}{25}{section.9}
\contentsline {subsection}{\numberline {9.1}El \textit {parser} m\IeC {\'a}s r\IeC {\'a}pido del mundo}{25}{subsection.9.1}
\contentsline {subsection}{\numberline {9.2}Checklist para corregir un Wrong Answer}{26}{subsection.9.2}
\contentsline {subsection}{\numberline {9.3}Redondeo de dobles}{27}{subsection.9.3}
\contentsline {subsubsection}{\numberline {9.3.1}Convertir un doble al entero m\IeC {\'a}s cercano}{27}{subsubsection.9.3.1}
\contentsline {subsubsection}{\numberline {9.3.2}Redondear un doble a cierto n\IeC {\'u}mero de cifras de precisi\IeC {\'o}n}{28}{subsubsection.9.3.2}
\contentsline {section}{\numberline {10}Java}{28}{section.10}
\contentsline {subsection}{\numberline {10.1}Entrada desde entrada est\IeC {\'a}ndar}{28}{subsection.10.1}
\contentsline {subsection}{\numberline {10.2}Entrada desde archivo}{29}{subsection.10.2}
\contentsline {subsection}{\numberline {10.3}Mapas y sets}{29}{subsection.10.3}
\contentsline {subsection}{\numberline {10.4}Colas de prioridad}{30}{subsection.10.4}
\contentsline {section}{\numberline {11}C++}{31}{section.11}
\contentsline {subsection}{\numberline {11.1}Entrada desde archivo}{31}{subsection.11.1}
\contentsline {subsection}{\numberline {11.2}Strings con caract\IeC {\'e}res especiales}{32}{subsection.11.2}